|
In theoretical computer science and formal language theory, a regular tree grammar (RTG) is a formal grammar that describes a set of directed trees, or terms. A regular word grammar can be seen as a special kind of regular tree grammar, describing a set of single-path trees. ==Definition== A regular tree grammar ''G'' is defined by the tuple ''G'' = (''N'', Σ, ''Z'', ''P''), where * ''N'' is a set of nonterminals, * Σ is a ranked alphabet (i.e., an alphabet whose symbols have an associated arity) disjoint from ''N'', * ''Z'' is the starting nonterminal, with ''Z'' ∈ ''N'', and * ''P'' is a set of productions of the form ''A'' → ''t'', with ''A'' ∈ ''N'', and ''t'' ∈ ''T''Σ(''N''), where ''T''Σ(''N'') is the associated term algebra, i.e. the set of all trees composed from symbols in Σ ∪ ''N'' according to their arities, where nonterminals are considered nullary. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「regular tree grammar」の詳細全文を読む スポンサード リンク
|